package com.example.leetcode;

import java.util.Arrays;

//有效三角形
public class Demo0611 {

    public static void main(String[] args) {
        System.out.println(triangleNumber3(new int[]{4,2,3,4}));
    }

    //自己枚举思路
    public static int triangleNumber1(int[] nums) {
        Arrays.sort(nums);
        int result=0;
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i+1; j < nums.length-1; j++) {
                for (int k = j+1; k <nums.length ; k++) {
                    if (nums[i]+nums[j]>nums[k]){
                        result++;
                    }
                }
            }
        }

        return result;
    }

    //排序二分查找
    public static int triangleNumber2(int[] nums) {
        int len=nums.length;
        Arrays.sort(nums);
        int result=0;

        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                int left=j+1,right=len-1,k=j;
                while (left<=right){
                    int mid=(left+right)/2;
                    if (nums[mid]<nums[i]+nums[j]){
                        k=mid;
                        left=mid+1;
                    }else {
                        right=mid-1;
                    }
                }

                result+=k-j;
            }
        }

        return result;
    }

    //排序双指针
    public static int triangleNumber3(int[] nums) {
        int len=nums.length;
        Arrays.sort(nums);
        int result=0;

        for (int i = 0; i < len; i++) {
            int k=i+1;
            for (int j = i+1; j < len; j++) {
                while (k+1<len && nums[k+1]<nums[i]+nums[j]){
                    k++;
                }
                result+=Math.max(k-j,0);
            }
        }

        return result;
    }
}
